Location Set Covering Problem (LSCP) - Real World Facility Location Problem

geospatial

map

spatial optimization

Introduction

Location Set Covering Problem (LSCP) fall within a class of problems known as set covering problems. The set covering problem class is an NP-hard problem within the combinatorial optimization space. These problems typically aim at minimizing the number of sets within a space that cover all the demand within that space.

The Location Set Covering Problem is described by Toregas et al. (1971). There they show that emergency services must be placed according to a response time, since there is a allowable maximum service time for handling emergency activities. Therefore the LSCP model was proprosed whereby

the minimum number of facilities determined and locaten so that every demand area is covered within a predefined maximal service distance or time

(Church and Murray, 2018).

The general scenarios for this project can be stated as: store sites should supply the demand in this census tract considering the distance between the two sets of sites: demand points and candidate supply sites. Four fundamental facility location models are utilized to highlight varying outcomes dependent on objectives: LSCP (Location Set Covering Problem), MCLP (Maximal Coverage Location Problem), P-Median and P-Center.

Location Set Covering Problem (LSCP)

Location Set Covering is a problem realized by Toregas, et al. (1971). He figured out that emergency services must have placed according to a response time, since, there is a allowable maximum service time when it’s discussed how handle an emergency activity. Minimize the number of facilities needed and locate them so that every demand area is covered within a predefined maximal service distance or time. Since the model needs a distance cost matrix we should define some variables.

Maximal Coverage Location Problem (MCLP)

LSCP try to minimize the amount of facilities candidate sites in a maximum service standard but then arise another problem: the budget. Sometimes it requires many facilities sites to reach a complete coverage, and there are circumstances when the resources are not available and it’s plausible to know how much coverage we can reach using a exact number of facilities. MCLP class try to solve this problem:

Maximize the amount of demand covered within a maximal service distance or time standard by locating a fixed number of facilities self.

P-Center Problem

Hakimi (1964) introduced the absolute center problem to locate a police station or a hospital such that the maximum distance of the station to a set of communities connected by a highway system is minimized. Hakimi (1965) generalizes the absolute center problem to the p-center problem.

P-Median Problem

Hakimi (1965) proposed this model thinking about locating telephone switching centers. Then the objective was to minimize the total length of wire serving all customers while locating telephone witching centers, assuming that each customer would be connected by wire to the closest switching center. Locate a fixed number of facilities such that the resulting sum of travel distances is minimized

Dataset

Load dataset

For this project, we will solve mulitple real world facility location problems using a dataset describing an area of census tract 205, San Francisco.

The problem is composed by 4 dataset:

• network_distance is the calculus of distance between facility candidate sites calculated by ArcGIS Network Analyst Extension
• demand_points represents the demand points with some important features for the facility location problem like population
• facility_points represents the stores that are candidate facility sites
• study_area is the polygon of census tract 205.

network_distance = pd.read_csv(r"..\map\map_service_area\SF_network_distance_candidateStore_16_censusTract_205_new.csv")

demand_points = pd.read_csv(r"..\map_service_area\SF_demand_205_centroid_uniform_weight.csv", index_col=0)
demand_points_gdf = gpd.GeoDataFrame( demand_points,geometry=gpd.points_from_xy(demand_points.long, demand_points.lat),).sort_values(by=['NAME']).reset_index()

facility_points = pd.read_csv(r"..\map_service_area\SF_store_site_16_longlat.csv", index_col=0)
facility_points_gdf = gpd.GeoDataFrame( facility_points, geometry=gpd.points_from_xy(facility_points.long, facility_points.lat),).sort_values(by=['NAME']).reset_index()

study_area = gpd.read_file(r"..\map_service_area\ServiceAreas_4.shp").dissolve()

network distance

demand points

facility points

polygon of census tract 205

Data Preparation

Before running any analysis, we need to ensure that our data is well-structured and ready for processing. This involves key preprocessing steps that transform raw datasets into a usable format for modeling. Here’s how we do it:

• creating a cost matrix, The first step is to pivot the network_distance dataframe into a cost matrix. This matrix represents the travel distance between different locations in our dataset, making it easier to analyze accessibility and connectivity.
• at demand_points dataset, we need a way to quantify demand in each area. In this case, we use population data from the year 2000 as a proxy for demand weight.

Defining Key Parameters

To fine-tune our analysis, we set a few important parameters that guide facility placement decisions:

• Service Distance (service_dist = 5000)
  • Each facility can serve a maximum radius of 5,000 meters (or 5 km).
  • Any demand point outside this radius will not be considered directly reachable.
  • This ensures realistic coverage for service areas, balancing accessibility with efficiency.
• Number of Facilities (p_facility = 4)
  • We assume that only 4 facilities will be placed in this area.
  • This constraint forces an optimization process—where to position these 4 facilities to maximize service coverage?

network distance matrics

The Code

By calling maps.spatial_cluster_opt, we can identify the optimal store locations to serve all of the demands.

result, model, fac2cli, fac2cli_idx = maps.spatial_cluster_opt(main_data=cost_matrix, types='lscp',threshold=service_dist)

This function requires the following parameters:

• main_data (string): Data location and value
• weights (list): list of value that we want to maximize
• types (string): Type of optimization
• threshold (int): the minimum number of point each region must have
• p_facilities (int): total point (i.e. medical locations )
• max_radius (int): maximum radius for each point

Then, by using maps.plot_cluster_opt we can plot the results to identify which stores were selected and what part of the population they are serving.

maps.plot_cluster_opt(model=result,facility_points=medical_center_locs,
                    demand_points=patient_locs,map_area=streets_gpd,p_facilities=4
                    fac2cli_idx=[],types ='pulp',title="LSCP - Cost Matrix Solution"
                    center_map=[])

This function requires the following parameters:

• model (string): result of model
• facility_points (dataframe): facility location data

• demand_points (dataframe): demand or point location data

• map_area (dataframe): area map data
• fac2cli (dataframe): cost matrix

• p_facilities (int): total point (i.e. medical locations )

• fac2cli_idx (dataframe): cost matrix index
• types (string): type of plot
• title (string): title
• center_map (list):

The result

Location Set Covering Problem (LSCP)

Maximal Coverage Location Problem (MCLP)

MCLP Percentage Covered: 89.7560

P-Center Problem

problem objective: 7403.06

P-Median Problem

p-median mean weighted distance: 2982.1268

problem objective: 2848268129.7145

The plot above clearly demonstrates the key features of each location model:

• LSCP Overlapping clusters of clients associated with multiple facilities All clients covered by at least one facility.
• MCLP Overlapping clusters of clients associated with multiple facilities Potential for complete coverage, but not guranteed.
• p-median Tight and distinct clusters of client-facility relationships All clients allocated to exactly one facility
• p-center Loose and overlapping clusters of client-facility relationships All clients allocated to exactly one facility